package twobranchTree.lowestcommonancestor;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/06
 * @author 王光浩
 * @Thinking 使用递归+前序方式进行。
 * @Analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class Introduction {
	private int firstNode;
	private int secondNode;
	private TreeNode res;
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.firstNode=p.val;
        this.secondNode=q.val;
        res=root;
        recursively(res);
        return res;
    }
	private boolean recursively(TreeNode root) {
		if(root==null)
			return false;
		boolean left=recursively(root.left);
		boolean right=recursively(root.right);
		boolean middle=false;
		//根节点和左右子树中一个子树分别含有p、q节点
		if(root.val==firstNode || root.val==secondNode) {
			if(left==true || right==true)
				res=root;
			middle=true;
		}
		//两个左子树中分别含有p、q节点
		else if(left==true && right==true) {
			res=root;
		}
		return left || right || middle;
	}
}
